package com.alg;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: sun.hongliang
 * @create: 2020/01/17 17:03
 * <p>
 * ["LRUCache","put","get","put","get","get"]
 * [[1],[2,1],[2],[3,2],[2],[3]]
 * <p>
 * [null,null,1,null,1,2]
 * <p>
 * [null,null,1,null,-1,2]
 */
public class LRUCache {

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(1);//null
        cache.put(2, 1);//null
        cache.get(2);//1
        cache.put(3, 2);//null
        cache.get(2);
        cache.get(3);
    }

    private Map<Integer, Entry> cacheMap;
    private Entry head;
    private Entry tail;
    private int capacity;

    public LRUCache(int capacity) {
        cacheMap = new HashMap<>(capacity);
        this.capacity = capacity;
    }

    public int get(int key) {
        Entry entry = cacheMap.get(key);
        if (entry == null) {
            return -1;
        }
        moveToHead(entry);
        return entry.value;
    }

    private void moveToHead(Entry entry) {
        if (entry == head) return;
        if (entry == tail) {
            Entry pre = entry.pre;
            if (pre != null) {
                pre.next = null;
                entry.pre = null;
                tail = pre;
            }
        } else {
            Entry pre = entry.pre;
            if (pre != null) {
                pre.next = entry.next;
            }
            Entry next = entry.next;
            if (next != null) {
                next.pre = entry.pre;
            }
        }
        head.pre = entry;
        entry.next = head;
        head = entry;
    }


    public void put(int key, int value) {
        Entry entry = cacheMap.get(key);
        if (entry == null) {
            Entry newEntry = new Entry();
            newEntry.key = key;
            newEntry.value = value;
            cacheMap.put(key, newEntry);
            addHead(newEntry);
            if (cacheMap.size() > capacity) {
                cacheMap.remove(tail.key);
                removeTail();
            }
        } else {
            entry.value = value;
            moveToHead(entry);
        }
    }

    private void addHead(Entry newEntry) {
        if (head == null && tail == null) {
            head = newEntry;
            tail = newEntry;
            return;
        }
        head.pre = newEntry;
        newEntry.next = head;
        head = newEntry;
    }

    private void removeTail() {
        if (tail == null) return;
        Entry pre = tail.pre;
        if (pre == null) {
            head = null;
            tail = null;
        } else {
            pre.next = null;
            tail.pre = null;
            tail = pre;
        }
    }

    class Entry {
        Entry pre;
        Entry next;
        int key;
        int value;
    }
}
